package Data_Structure.MapAndSet;

import Data_Structure.MapAndSet.model.Node;

import java.util.*;

/**
 * @className: Test1
 * @author: 芃
 * @description: Map和Set 相关OJ习题
 * @date: 2023/8/20 17:34
 */
public class Test1 {
    public static void main1(String[] args) {

    }
    //6、字符串中第一个唯一字符
    public int firstUniqChar(String s) {
        int[] arr = new int[26];
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            int index = c - 97;
            arr[index]++;
        }
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (arr[c-97] == 1){
                return i;
            }
        }
        return -1;
    }

    //5、前K个高频的单词
    //思路：①先统计每个单词出现的次数
    //②然后建一个大小为K的小根堆，即root节点小于左右子树节点
    //③将map当中统计的数据放入小根堆
    //④最后将小根堆当中的数据存储到List当中返回
    public List<String> topKFrequent(String[] words, int k) {
        HashMap<String,Integer> map = new HashMap<>();
        //①统计
        for (String s: words) {
            if (map.containsKey(s)){
                int val = map.get(s);
                val++;
                map.put(s,val);
            }else {
                map.put(s,1);
            }
        }
        //②建堆+指定比较规则
        PriorityQueue<Map.Entry<String,Integer>> queue = new PriorityQueue<>(k, new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if (o1.getValue().compareTo(o2.getValue()) == 0){//如果次数相同，则比较字符串大小
                    return o2.getKey().compareTo(o1.getKey());
                }
                return o1.getValue() - o2.getValue();
            }
        });
        //③放数据
        for (Map.Entry<String,Integer> entry: map.entrySet()) {
            if (queue.size()<k){
                queue.offer(entry);
            }else {
                Map.Entry<String,Integer> top = queue.peek();
                if (top.getValue().compareTo(entry.getValue()) == 0){//如果出现次数一致，就比较字符串大小
                    //字符串大小必然不会出现相同？为啥？因为字符串是作为map的key存储的呀，key必然是唯一的
                    if (top.getKey().compareTo(entry.getKey()) > 0){
                        queue.poll();
                        queue.offer(entry);
                    }
                }else {
                    if (top.getValue().compareTo(entry.getValue()) < 0){//走到这，说明值不相同，那就和堆顶比
                        //堆顶的元素，是整个堆出现次数最少的元素，如果比堆顶的元素出现次数大，那就把堆顶的元素出出去，把新的元素放进来
                        queue.poll();
                        queue.offer(entry);
                    }
                }
            }
        }
        //④获取小根堆里面的数据
        List<String> list = new ArrayList<>();
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            list.add(queue.poll().getKey());
        }
        //到这还没完，为啥？因为堆出元素时是最先出小的，即在前K个结果集中，最小的那个最先出
        //list是尾插，意味着出现次数最多的元素是最后出的，也就是在List的末尾存储着呢
        //那怎么办？
        Collections.reverse(list);//对整个集合进行反转
        //返回
        return list;
    }

    //4、旧键盘打字
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextLine()){
            String target = scanner.nextLine();
            String source = scanner.nextLine();
            String ret = checkBad(target,source);
            System.out.println(ret);
        }
        scanner.close();
    }
    public static String checkBad(String target,String source){
        HashSet<Character> set = new HashSet<>();
        HashSet<Character> res = new HashSet<>();
        StringBuilder stringBuilder = new StringBuilder();
        char[] ch1 = target.toUpperCase().toCharArray();
        char[] ch2 = source.toUpperCase().toCharArray();
        for (char value : ch2) {
            set.add(value);
        }
        for (char c : ch1) {
            if (!set.contains(c) && !res.contains(c)) {
                //说明不包含
                stringBuilder.append(c);
                res.add(c);
            }
        }
        return stringBuilder.toString();
    }

    //3、宝石和石头
    public int numJewelsInStones(String jewels, String stones) {
        HashSet<Character> set = new HashSet<>();
        char[] array = jewels.toCharArray();
        char[] check = stones.toCharArray();
        for (char c : array) {
            set.add(c);
        }
        int count = 0;
        for (int i = 0; i < stones.length(); i++) {
            if (set.contains(check[i])){
                count++;
            }
        }
        return count;
    }

    //2、复制带随机指针的链表
    public Node copyRandomList(Node head) {
        HashMap<Node,Node> map = new HashMap<>();
        Node cur = head;
        while (cur != null){
            Node node = new Node(cur.val);
            map.put(cur,node);
            cur = cur.next;
        }
        Node tmp = head;
        while (tmp != null){
            Node ret = map.get(tmp);
            ret.next = map.get(tmp.next);
            ret.random = map.get(tmp.random);
            tmp = tmp.next;
        }
        return map.get(head);
    }

    //1、只出现一次的数字
    public int singleNumber(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        for (int num : nums) {
            if (set.contains(num)) {
                set.remove(num);
            } else {
                set.add(num);
            }
        }
        for (int num : nums){
            if (set.contains(num)){
                return num;
            }
        }
        return -1;
    }
}
